package org.huawei260.basic.part_3_tree.tree;

/**
 * @Author: qingle
 * @Date: 2024/11/29-10:10
 * @Description: 3.1 二叉树与遍历
 *
 * 二叉树的关键特性：每个节点最多只有2个子节点，左子节点和右子节点。
 * 每一层的节点数是上一层的两倍
 *
 * 二叉树的遍历：前序遍历、中序遍历、后序遍历、层序遍历
 * 前序遍历：根节点->左子树->右子树
 * 中序遍历：左子树->根节点->右子树
 * 后序遍历：左子树->右子树->根节点
 * 层序遍历：按层遍历
 * 前中后的逻辑顺序取决于根节点的位置
 *
 * 按照层序遍历的定义，我们不能先遍历叶子节点，然后再遍历根节点，因为这违背了层序遍历的基本原则。层序遍历的步骤如下：
 *
 * 从根节点开始。
 * 访问根节点。
 * 将根节点的所有子节点加入队列。
 * 从队列中取出一个节点，访问该节点。
 * 将该节点的所有子节点加入队列。
 * 重复步骤4和5，直到队列为空。
 *
 * 适用对象的引用表示二叉树是一种常见的方法。
 * 1.创建一个节点类（Node class)
 * 2.创建一个二叉树类（BinaryTree class)
 * 3.创建一个二叉树对象（BinaryTree object)
 * 4.使用递归算法实现遍历
 * 5.使用队列实现层序遍历
 * 6.使用栈实现后序遍历
 * 7.使用堆栈实现前序遍历和后序遍历
 * 8.使用队列实现中序遍历
 * 9.使用递归算法实现树的深度和宽度
 * 10.使用递归算法实现树的遍历
 * 11.使用递归算法实现树的搜索和删除
 * 12.使用递归算法实现树的复制
 * 13.使用递归算法实现树的排序
 * 14.使用递归算法实现树的比较
 * 15.使用递归算法实现树的合并
 * 16.使用递归算法实现树的分割
 *
 * @Version: 1.0
 */
public class BinaryTreeAndTraversal {

	// 二叉树的遍历
	public static class BinaryTree {
		TreeNode root;// 根节点

		// 实现前序遍历
		void preOrder(TreeNode node) {
			// 非空判断
			if(node == null) return;

			System.out.println(node.value + " ");// 访问根节点的value
			// 递归实现,递归思想
			preOrder(node.left);// 递归遍历左子树
			preOrder(node.right);// 递归遍历右子树
		}

		// preOrder() 方法的职责是： 递归实现前序遍历
		// 您可以方便地从外部调用前序遍历，而不需要直接操作根节点或了解递归实现的细节。它提供了一个简单的接口，使得遍历过程更加模块化和易于使用。
		void preOrder() {
			preOrder(root);
		}
	}

	public static void main(String[] args) {
		BinaryTree binaryTree = new BinaryTree();
		// 传入根节点为1
		TreeNode treeNode = new TreeNode(1);
		binaryTree.root = treeNode;
		binaryTree.root.left = new TreeNode(2);
		binaryTree.root.right = new TreeNode(3);

		binaryTree.root.left.left = new TreeNode(4);
		binaryTree.root.left.right = new TreeNode(5);
		binaryTree.root.right.left = new TreeNode(6);
		binaryTree.root.right.right = new TreeNode(7);

		System.out.println("前序遍历的结果为：");
		binaryTree.preOrder(treeNode);

	}

}
